package Test;

import java.util.Deque;
import java.util.LinkedList;

public class Test3 {

    public static int[] getMaxSlidingWindow(int[] nums, int k){
        if(nums.length < 1 || k < 1 || k > nums.length){
            return null;
        }

        int n = nums.length;
        int[] res = new int[n - k +1];
        Deque<Integer> deque = new LinkedList<>();
        int index = 0;
        for(int i = 0; i < n; i++){
            // 队列头过期
            if(!deque.isEmpty() && deque.peekFirst() <= i - k){
                deque.pollFirst();
            }

            while(!deque.isEmpty() && nums[i]>nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);

            if(i >= k-1){// 开始记录窗口最大值
                res[index++] = nums[deque.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1,-1};
        int[] res = getMaxSlidingWindow(nums, 1);
        for(int cur : res){
            System.out.print( cur +", ");
        }
    }
}
